package chapter01;

public class MergeTwoLists {
       public class ListNode {
       int val;
       ListNode next;
       ListNode() {}
       ListNode(int val) { this.val = val; }
       ListNode(int val, ListNode next) { this.val = val; this.next = next; }
       }

    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode p=list1,q=list2,head=new ListNode(),newList=head;
        if(list1==null&&list2==null){
            return null;
        }
        while(p!=null||q!=null){
            if(p.val< q.val){
                head.next=p;
                head=p;
                p=p.next;
            }else{
                head.next=q;
                head=q;
                q=q.next;
            }
        }
        head.next=p!=null?p:q;
        newList=head.next;
        head=null;
        return newList;
    }
}
